﻿//公共头文件，有相同的内容写在这个里面，包含这个文件即可
#pragma once
#include <iostream>
#include <vector>
#include <ctime>
#include <thread>
#include <cassert>
#include <mutex>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <cstdint>    // uintptr_t
#include <cstring>    // memset


#ifdef _WIN32
#include <windows.h>
#else
// linux下brk mmap等
#endif

using std::cout;
using std::endl;

static const size_t MAX_BYTES = 256 * 1024; //目前保证最大内存块申请不超过256kb
static const size_t NFREE_LIST = 208;       //根据最大内存块申请不超过256kb和对齐规则，算出每个thread cache下最多有208个自由链表桶
static const size_t NPAGES = 129;
static const size_t PAGE_SHIFT = 13;		//8kb,即2^13byte，假设1页就是8kb



#ifdef _WIN64 //ifdef不能判断_WIN32,因为64位机器_WIN32与_WIN64都有定义，会导致64位机器也进#ifdef WIN32
	typedef unsigned long long PAGE_ID;
#elif _WIN32
	typedef size_t PAGE_ID;
#else
	//linux...
#endif

//malloc实际也是一个内存池，下面可以脱离malloc
// 直接去堆上按页申请空间
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
	void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE,
		PAGE_READWRITE);
#else
	// linux下brk mmap等
#endif //只是ifdef的结束标志


	if (ptr == nullptr)
		throw std::bad_alloc();
	return ptr;
}

inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else
	// sbrk unmmap等
#endif
}
	


//获取内存对象的头4字节或者8字节
static void*& NextObj(void* obj)
{
	return *(void**)obj;
}

class FreeList
{
public:
	//回收
	void Push(void* obj)
	{
		assert(obj);
		//头插
		//*(void**)obj = _freeList;
		NextObj(obj) = _freeList;
		_freeList = obj;

		++_size;
	}

	//从自由链表中头删
	void* Pop()
	{
		assert(_freeList);
		//头删
		void* obj = _freeList;
		_freeList = NextObj(obj);

		--_size;

		return obj; //返回头删后从自由链表拿出来的内存
	}

	//将从central cache申请到的一串链表（一个一个的内存块）头插到当前thread cache的自由链表下
	void PushRange(void* start, void* end,size_t n)
	{
		NextObj(end) = _freeList;
		_freeList = start;

		////测试验证+条件断点
		//int i = 0;
		//void* cur = start;
		//while (cur)
		//{
		//	cur = NextObj(cur);
		//	++i;
		//}
		//if (n != i)
		//{
		//	int x = 0;
		//}

		_size += n;
	}

	void PopRange(void*& start, void*& end, size_t n)
	{
		assert(n <= _size);
		start = _freeList;
		end = start;
		for (int i = 0; i < n - 1; i++)
		{
			end = NextObj(end);
		}
		_freeList = NextObj(end);
		NextObj(end) = nullptr;
		_size -= n;

	}

	bool Empty()
	{
		return _freeList == nullptr;
	}

	size_t& MaxSize()
	{
		return _maxSize; 
	}

	size_t Size()
	{
		return _size;
	}
private:
	void* _freeList = nullptr; //给了缺省值了，就算不写调用默认构造初始化，会先用这个缺省值初始化，这样就不会随机值了
	size_t _maxSize = 1;      //保证一次不会像Central Cache要太多块内存
	size_t _size = 0; 			  //自由链表长度
};

// 管理对齐和映射等关系
//这个类不需要成员变量，函数弄成static成员函数就可以，还可以加工inline
class SizeClass
{
public:
	// 整体控制在最多10%左右的内碎片浪费
	// [1,128]					8byte对齐         freelist[0,16)  相当于1-8字节映射下标为0的桶即1号桶
	// [128+1,1024]				16byte对齐  		  freelist[16,72)
	// [1024+1,8*1024]			128byte对齐       freelist[72,128)
	// [8*1024+1,64*1024]		1024byte对齐      freelist[128,184)
	// [64*1024+1,256*1024]		8*1024byte对齐    freelist[184,208)

	//都是8字节对齐？
	//桶太多了

	//10%左右的内碎片浪费是怎么算的呢？
	//1.首先，开始的对齐必须从8字节开始，因为申请的内存对象至少要有8字节（主要满足64位，32位只需4字节，8字节也够了）存下一个节点的指针
	//2.开始的8字节对齐就不用算浪费了，因为避免不了，尽管是2字节对齐，只用1字节也造成了50%内碎片浪费，能保证后面的大部分对齐浪费是不多的即可
	//3.后面的例如16字节对齐，假设对象需要129字节空间，那就会给对象128+16即144大小空间，所以浪费了15字节，15/144大概就是10%左右的浪费，后面都是这样算

	//自由链表有多少个怎么算？也就是有多少个桶？
	//128/8=16个桶，往下是1024-128=896,896/16=56桶,以此类推
	 

	//正常版--获取对齐后，要给的大小
	/*size_t _RoundUp(size_t size, size_t alignNum) //align对齐
	{
		size_t alignSize;
		if (size % alignNum != 0)
		{
			alignSize = (size / alignNum + 1) * alignNum;
		}
		else
		{
			alignSize = size;
		}
		return alignSize;
	}*/

	//高手版--获取对齐后，要给的大小
	static inline size_t _RoundUp(size_t bytes, size_t alignNum) 
	{
		//可以举例子试一下，总体思路就是将bytes的不足对齐的位给&成0，这样只剩下能对齐的位与能对齐的位的倍数了
		//每次申请空间都要算对齐，位运算更快
		return ((bytes+alignNum - 1) & ~(alignNum - 1)); 
	}

	//选择要用哪种对齐方式，并返回对齐后给出的内存
	static inline size_t RoundUp(size_t size)
	{
		if (size <= 128)
		{
			return _RoundUp(size, 8);
		}
		else if (size <= 1024)
		{
			return _RoundUp(size, 16);
		}
		else if (size <= 1024*8)
		{
			return _RoundUp(size, 128);
		}
		else if (size <= 1024*64)
		{
			return _RoundUp(size, 1024);
		}
		else if (size <= 1024*256)
		{
			return _RoundUp(size, 8*1024);
		}
		else
		{
			//以页为单位对齐
			return _RoundUp(size, 1<<PAGE_SHIFT);
		}
	}

	//普通版
	//static size_t _Index(size_t bytes, size_t alignNum)
	//{
	//	if (bytes % alignNum == 0)
	//	{
	//		return bytes / alignNum - 1; //例如大小为8字节的空间，应该在下标为0的桶
	//	}
	//	else
	//	{
	//		return bytes / alignNum;
	//	}
	//}

	//高手版
	static inline size_t _Index(size_t bytes, size_t align_shift)
	{
		//可以举例子，例如bytes是1，align_shift是3，则就是1+8-1，然后右移3位得1，再减1得下标0，所以1映射到下标为0的自由链表桶
		return ((bytes + ((size_t)1 << align_shift) - 1) >> align_shift) - 1;
	}

	// 计算映射的哪一个自由链表桶
	static inline size_t Index(size_t bytes)
	{
		assert(bytes <= MAX_BYTES);
		// 每个区间有多少个链
		static int group_array[4] = { 16, 56, 56, 56 };
		if (bytes <= 128) {
			return _Index(bytes, 3);
		}
		else if (bytes <= 1024) {
			return _Index(bytes - 128, 4) + group_array[0];
		}
		else if (bytes <= 8 * 1024) {
			return _Index(bytes - 1024, 7) + group_array[1] + group_array[0];
		}
		else if (bytes <= 64 * 1024) {
			return _Index(bytes - 8 * 1024, 10) + group_array[2] + group_array[1]
				+ group_array[0];
		}
		else if (bytes <= 256 * 1024) {
			return _Index(bytes - 64 * 1024, 13) + group_array[3] +
				group_array[2] + group_array[1] + group_array[0];
		}
		else {
			assert(false);
		}
		return -1;
	}

	// 一次thread cache从中心缓存获取多少个
	static size_t NumMoveSize(size_t size)
	{
		assert(size > 0);
		// [2, 512]，一次批量移动多少个对象的(慢启动)上限值
		// 小对象一次批量上限高
		// 小对象一次批量上限低
		size_t num = MAX_BYTES / size;
		if (num < 2)
			num = 2;
		if (num > 512)
			num = 512;
		return num;
	}

	// 计算一次向系统获取几个页
	// 单个对象 8byte
	// ...
	// 单个对象 256KB,假设一次要256kb，那就是要64页,越大要的页数越多，方便合并
	static size_t NumMovePage(size_t size)
	{
		size_t num = NumMoveSize(size);
		size_t npage = num * size;
		npage >>= PAGE_SHIFT; //除以1页也就是8kb
		if (npage == 0)
			npage = 1;
		return npage;
	}
};


//管理多个连续页大块内存跨度结构
//写在Common是因为CentralCache与PageCache都要用
//不写Span的构造，要给缺省值，不然都是随机值
struct Span
{
	//如果一个页是8kb,那32位平台地址空间是4GB，能分2^32/2^13=2^19个页
	//64位平台地址空间是8GB，能分2^64/2^13=2^51个页，但是这里(32位是2^32-1)64位size_t大小是2^64-1好像也是够的，不用条件编译也行好像
	PAGE_ID _pageId = 0;		//大块内存起始页的页号

	size_t _n = 0;				//页数

	Span* _next = nullptr;		//双向链表的结构
	Span* _prev = nullptr;

	size_t _useCount = 0;		//切好的小块内存，被分配给thread cache的计数

	void* _freeList = nullptr;	//切好的小块内存的自由链表,span下的链表

	bool _isUse = false;		//是否在被使用

	size_t _objSize = 0;		//切好的小对象的大小

};

//带头双向循环链表,链接多个span，每个span下面还有一个链表_freeList
class SpanList
{
public:
	SpanList()
	{
		_head = new Span;
		_head->_next = _head;
		_head->_prev = _head;
	}

	Span* Begin()
	{
		return _head->_next;
	}

	Span* End()
	{
		return _head;
	}

	bool Empty()
	{
		return _head == _head->_next;
	}

	void PushFront(Span* span)
	{
		Insert(Begin(), span);
	}

	Span* PopFront()
	{
		Span* front = _head->_next;
		Erase(front);
		return front;
	}

	//在pos前插入
	void Insert(Span* pos, Span* newSpan)
	{
		assert(pos);
		assert(newSpan);

		Span* prev = pos->_prev;
		prev->_next = newSpan;
		newSpan->_prev = prev;
		newSpan->_next = pos;
		pos->_prev = newSpan;
	}

	//这里pos不用真的delete掉，因为这里删除span其实要做的是还给page cache（后面再做），不需要真的删除
	void Erase(Span* pos)
	{
		assert(pos);

		assert(pos != _head);
		//1.条件断点
		//2.查看栈帧
		//if (pos == _head)
		//{
		//	int x = 0; //无所谓的语句，只是为了打断点 
		//}

		Span* prev = pos->_prev;
		Span* next = pos->_next;

		prev->_next = next;
		next->_prev = prev;
	}
private:
	Span* _head;	 //哨兵位头节点
public:
	std::mutex _mtx; //桶锁
};